LeetCode题解（一）—— Binary Search

发表于 | 分类于 | | 热度: ℃
字数统计: 5,860 | 阅读时长 ≈ 24

0x00 二分查找模板

二分查找是在一定范围内查找满足要求元素较为高效的一种方法，其时间复杂度为O(logn)级别，关于二分法模板和主要问题分析可以参考以下博客：Binary Search。

对于三种常见模板的比较如下：

二分查找法.png-340.6kB

0x01 题解

下面结合一些最近在LeetCode上刷过的二分查找题目的题解分析该方法的细节。

LeetCode-69.Sqrt(x)

题目链接

69.Sqrt(x)

题目描述

Difficulty: Easy

69.PNG-23.3kB

该题目要求返回对提供输入开二次方的向下取整值，可以使用二分法和牛顿迭代法两种方法解题。

二分法

思路分析

使用二分法进行平方根搜索，首先需要确定搜索的范围。由于一个数字的平方根显然不会大于其本身，故可以设置left = 0, right = x。不过直觉告诉我们，一个数字的平方根最多不会超过其一半。我们需要计算满足这一条件的边界范围，解方程(a/2)^2 >= a，我们得到a<=0或a>=4，显然当x>=4的时候，可将right设置为x/2。对于特值0-3，其平方根分别为0，1，1，1，我们可以加上条件判断语句if(x<4){return x == 0 ? 0: 1;}。

对于剩下的情况，我们直接使用while(left < right)对应的模板即可，需要注意的是，由于不确定输入值x的范围，如果使用int类型的left,right和mid，容易出现溢出异常，所以我们统一选择long数据类型。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {

    public int mySqrt(int x) {
        long left = 0;
        long right = Integer.MAX_VALUE;
        while (left < right) {
            long mid = (left + right + 1) >>> 1;
            long square = mid * mid;
            if (square > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return (int) left;
    }
}

牛顿迭代法

思路分析

使用牛顿法可以得到一个正实数的算数平方根，因为题目中要求“结果只保留整数部分”，因此我们把使用牛顿法得到的浮点数转换成整数即可。首先给出牛顿法的思想：

在迭代过程中，以直线代替曲线，用一阶泰勒展开式（即在当前点的切线）代替原曲线，求直线与x轴的交点，重复这个过程直到收敛。

迭代公式的计算和推理证明如下：

应用牛顿法解平方根问题，可令f(x) = x^2 - a

由f(x) ≈ f(x0) + (x-x0)*f’(x0) 该式子可由斜率的定义推导出

令f(x) = 0，得f(x0) + (x-x0)*f’(x0) = 0

x = x0 - f(x0)/f’(x0) = x0 - (x0^2 - a) / (2*x0) = (x0 + a/x0) / 2

最终得到的迭代公式可表示为x0 = (x0+a/x0)/2

代码编写过程中对于初值可以任意选取，但是如果初值选择负数，有可能得到负数平方根，所以初值尽量选择非负数。

牛顿迭代法主要用于求方程的根和求解最优化问题。该方法求解开方问题的详细说明可以参考知乎文章：如何通俗易懂地讲解牛顿迭代法求开方？数值分析？

解题代码

1
2
3
4
5
6
7
8
9
class Solution {
    public int mySqrt(int x) {
        long m = x;
        while((m*m)>x){
            m = (m+x/m)/2;
        }
        return (int)m;
    }
}

LeetCode-153.Find Minimum in Rotated Sorted Array

题目链接

153.Find Minimum in Rotated Sorted Array

题目描述

Difficulty: Medium

153.PNG-18.1kB

思路分析

本题目的输入为一个按任意顺序截断后重新拼接的有序数组，即整体数组由两个升序的有序数组组成，待求值为最小元素即两个数组的拼接点元素。

为了加快搜索效率，我们首先处理特殊情况，即输入数组整体为一个升序数组，即满足nums[0] < nums[nums.length-1]，该情况下返回nums[0]即可。

如果输入数组由两个升序数组组成，我们可以使用二分查找的方法，设left = 0, right = nums.length - 1，每次循环先将nums[mid]与nums[mid+1]进行比较，如果nums[mid] > nums[mid+1]，则后者必为拼接点元素，直接返回即可。否则将nums[mid]与nums[0]比较，若前者大，说明mid位于左侧升序数组中，需要将mid右移，故右移left边界；若前者小，说明mid位于右侧升序数组中，需要将mid左移，故左移right边界。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findMin(int[] nums) {
        int length = nums.length - 1;
        if(nums[0] <= nums[length]){
            return nums[0];
        }
        int left = 0;
        int right = length;
        while(left < right){
            int mid = (left + right) >>> 1;
            if(nums[mid] > nums[mid+1]){
                return nums[mid+1];
            }
            else if(nums[mid] > nums[0]){
                left = mid + 1;
            }
            else if(nums[mid] < nums[0]){
                right = mid;
            }
        }
        return -1;
    }
}

LeetCode-658.Find K Closest Elements

题目链接

658.Find K Closest Elements

题目描述

Difficulty: Medium

658.PNG-35.5kB

思路分析

本题目的输入为一个升序排序数组和两个整数k,x，题目要求返回数组中与整数x距离最近的k个元素组成的升序数组，如果符合要求的数组有多个，则返回内部元素较小的那个。

初步思路
刚拿到题目的时候大致将可能出现的结果分成了两种情况：第一种是所给目标x小于所给数组的最小值或大于所给数组的最大值，这样只需要取数组的前k个或后k个元素即可满足要求。第二种是所给目标x在数组中，这样需要讨论x实际所处的位置即x前是否有k-1个元素。

深入分析
如果按照上面最初的思路进行讨论会发现分支情况过多，也就是说需要较多的else if结构。如果我们应用所给数组的有序性和不重复性来解题，运用算法提取一段数组元素，解题效率将会大大提升。

使用二分法解题过程中需要明确两点：左右边界何时需要移动以及如何移动。下面来讨论这两点问题。我们换一种思路，不使用二分法寻找待找元素x，而是找满足题目要求区间的起始元素t。寻找元素t过程中，我们引入类似滑动窗口的机制，将arr[mid]的值与待找元素x作差，将其与arr[mid+k]元素与x的差进行比较。如果前者的值小于等于后者，说明该窗口更贴近右侧（即与题目的smaller elements are always preferred相违背），需要向左移动，此时我们令right = mid从而实现窗口左移。如果前者的值大于后者，说明该窗口过于偏左，即不是与目标元素x最近的k个元素，此时我们令left = mid + 1从而实现窗口右移。

在窗口左移过程中还有一点需要注意，如果默认mid+k的值为合法下标，容易造成数组下标越界问题。我们还需要使用语句比较mid+k和length的大小，如果mid+k >= length，说明窗口偏右，无法提取符合要求的k个元素，将窗口左移即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> result = new ArrayList<Integer>();
        int left = 0;
        int length = arr.length;
        int right = length - 1;
        while(left < right){
            int mid = (left + right) >>> 1;
            if(mid + k >= length || Math.abs(arr[mid] - x) <= Math.abs(arr[mid+k] - x)){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        for(int i = left;i<left+k;i++){
            result.add(arr[i]);
        }
        return result;
    }
}

LeetCode-50.Pow(x,n)

题目链接

50.Pow(x,n)

题目描述

Difficulty: Medium

50.PNG-22.4kB

思路分析

本题输入为一个double类型的数字x和一个int类型的数字n，返回结果为pow(x, n)的值。最简单的想法就是直接进行连乘，但效率较低，无法通过时间限制。我们换一种思路，采用递归的方法求解，对于一个特定的整数次方n，由于整除运算具有向下取整的特性，其可以进行如下分解：x^n = x^(n/2)*x^(n/2)*x^(n%2)，我们只需要每次递归计算x^(n/2)和x^(n%2)，最后返回上式类型的乘积即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public double myPow(double x, int n) {
        if(n == 1){return x;}
        else if(n == 0){return 1.00000;}
        else if(n == -1){return 1/x;}

        double half = myPow(x, n/2);
        double rest = myPow(x, n%2);

        return half*half*rest;
    }
}

LeetCode-34.Find First and Last Position of Element in Sorted Array

题目链接

34.Find First and Last Position of Element in Sorted Array

题目描述

Difficulty: Medium

34.PNG-20.7kB

思路分析

拿到该题目后，根据题中所给的要求即将时间复杂度限制在log(n)水平，想到需要使用二分法。分析该题目，发现所给的数组为升序有序数组，并且其中有可能出现重复的元素。

初步的思路为先使用二分法寻找左边界或右边界，找到之后重新初始化left和right参数，再使用二分法找到另外一个边界。

由于返回的结果为数组，故先定义结果数组result = {-1, -1}，然后对所给的有序数组进行检测，如果为空数组或null，直接返回初始化的result。

然后先寻找右边界，关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while(left < right){
  int mid = (left + right) >>> 1;
  // 先找右边界
  if(nums[mid] == target){
     left = mid + 1;
  }
  else if(nums[mid] > target){
     right = mid;
  }
  else if(nums[mid] < target){
     left = mid + 1;
  }
}
// 这里如果跳出则left = mid = right，如果left==0且结束比较说明target < nums[0]，target不在nums序列中
if(left == 0){return result;}

如果nums[mid] < target，说明第一个可能的target必在mid的右侧（至少为mid+1）；如果nums[mid] == target，由于nums[mid]已经与target完成比较，故需要将left右移；如果nums[mid] > target，说明第一个可能的target必在mid的左侧。这里可能会出现一个问题，就是为什么不令right = mid + 1？

这里的写法可以追溯到初始时的left与right的赋值。这里令left = 0, right = nums.length，我们的搜索区间为[left, right)即左闭右开区间。如果需要改变right的值，显然我们已经完成nums[mid]与target的比较，由于区间右侧为开区间，不包括mid，故令right = mid而非right = mid+1。

while循环结束之后，我们添加了如下语句:

1
2
3
if(left == 0){
  return result;
}

该段代码也是右边界寻找算法中需要注意的细节。当target < nums[0]时，显然应该返回[-1,-1],该情况下左边界left并没有移动，即此时left == 0是成立的。那么除了正确返回未找到信息，该段代码还有什么用处呢？这就要结合下面的代码说明。

1
int right2 = nums[left-1] == target ? left-1 : -1;

这里right2即为找到的右边界，将其进行初始赋值是为了缩小寻找左边界过程中二分查找的范围，提高查找效率。由于每次为left赋值为left = mid + 1，这样当right == mid + 1时，显然满足right == left，循环跳出，这时就出现一个问题即nums[mid]并没有与target进行大小比较，于是需要增加一个nums[left-1]与target的比较。此时nums[left]与target一定不相等，而nums[left-1]与target可能相等。

继续回到上面提到的问题，如果不加上left == 0的处理语句，显然left-1 == -1，会发生数组下标越界问题。

e5c8721ea29865f337e815de97aa57f58498843300f984860e3769c3768a2a7e-1.png-24.5kB

对right2和left2进行赋值后，继续使用二分法寻找左边界，最终返回result数组即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if(nums == null || nums.length == 0){return result;}
        int left = 0;
        int right = nums.length;
        while(left < right){
            int mid = (left + right) >>> 1;
            // 先找右边界
            if(nums[mid] == target){
                left = mid + 1;
            }
            else if(nums[mid] > target){
                right = mid;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }
        }
        // 这里如果跳出则left = mid = right，如果left==0且结束比较说明target < nums[0]，target不在nums序列中
        if(left == 0){return result;}
        int right2 = nums[left-1] == target ? left-1 : -1;
        // 最终得到的右边界为left亦即right
        // 再找左边界
        if(right2 == -1){return result;}
        result[1] = right2;
        int left2 = 0;
        while(left2 < right2){
            int mid2 = (left2 + right2) >>> 1;
            // 寻找左边界
            if(nums[mid2] == target){
                right2 = mid2;
            }
            else if(nums[mid2] > target){
                right2 = mid2;
            }
            else if(nums[mid2] < target){
                left2 = mid2 + 1;
            }
        }
        // 最终得到左边界为left2
        result[0] = left2;
        return result;
    }
}

LeetCode-154.Find Minimum in Rotated Sorted Array II

题目链接

154.Find Minimum in Rotated Sorted Array II

题目描述

Difficulty: Hard

154.PNG-24.5kB

思路分析

本题的输入为旋转之后的有序数组，值得注意的是，输入数组中存在部分重复的元素，要求寻找整个数组中最小的元素。

旋转数组nums可以被拆分成左右两个升序数组nums1,nums2，并且满足nums1任意元素 >= nums2任意元素，因此考虑二分法寻找此数组的分界点nums[i]（即为nums2的首个元素）。

我们分析可能出现的三种情况：

  • 第一种情况：当nums[mid] > nums[right]时，mid一定处于左侧排序数组nums1中，待寻找元素下标i一定满足mid < i <= right，因此执行left = mid + 1；

  • 第二种情况：当nums[mid] < nums[right]时，mid一定处于右侧排序数组nums2中，待寻找元素下标i一定满足left < i <= mid，因此执行right = mid；

  • 第三种情况：当nums[mid] == nums[right]时，此时由于此题中数组的元素可重复，难以判断分界点i指针区间。例如[1,0,1,1,1]和[1,1,1,0,1]这两种情况，无法判断mid在哪个排序数组中，因此无法确定将区间左移还是右移。

    针对此种情况，我们采用right = right - 1来解决，证明如下：

    • 此操作不会使数组越界，因为迭代条件保证了right > left >= 0

    • 此操作不会使最小值丢失，假设nums[right]是最小值，此时有两种可能情况：

      若nums[right]是唯一最小值，那就不可能满足判断条件nums[mid] == nums[right]（因为mid < right）；

      若nums[right]不是唯一最小值，由于mid < right而nums[mid] == nums[right]，即还有最小值存在于[left, right-1]区间，因此不会丢失最小值。

该算法的时间复杂度为O(logN)，在特例情况下会退化到O(N)（例如[2，2，2，2]）。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = (left + right) >>> 1;
            if(nums[mid] > nums[right]){
                // 所求的最小值存在于(mid, right]之间，将滑动窗口右移
                left = mid + 1;
            }
            else if(nums[mid] < nums[right]){
                // 说明所求的最小值存在于[mid, right)之间，将滑动窗口左移
                right = mid;
            }
            else{
                // 如果nums[mid] == nums[right]，最小值既可能在mid左侧，也可能在其右侧
                // 令right = right - 1，将滑动窗口左移，如果存在唯一最小值该部分语句不会执行
                // 如果存在多个相同的最小值，则右推至区间内只剩唯一最小值
                // 最终都会返回该最小值
                right = right - 1;
            }
        }
        return nums[left];
    }
}

LeetCode-410.Split Array Largest Sum

题目链接

410.Split Array Largest Sum

题目描述

Difficulty: Hard

410.PNG-29.1kB

思路分析

该题解参考了精选题解中使用C++实现的算法:二分查找，并对其中一些迷惑的地方进行说明。

下面进行思路分析及代码细节梳理：

二分查找的边界如何确定？

二分查找类题目一般具有一些特征，最典型的是对时间复杂度具有O(logn)的需求，还有较为关键的一点是具有明确的查找上下界以及可供二分的判断标志。

针对本题，由题目中提供的条件可知，数组中所有的元素均为非负整数。题目需要将大数组划分为m个小数组，并保证此种划分方法得到的最大的子数组元素和取到最小值，而进行子数组划分过程中必定有一个子数组包含待划分数组中元素的最大值max(nums[i])，所以子数组元素和的最小值为max(nums[i])。确定左边界后我们来考虑右边界，显然当m等于1时，数组中所有元素之和即为最大值，故右边界可以取sum(nums[i])。

上述部分使用了以下代码：

1
2
3
4
5
6
int left = 0;
int right = 0;
for(Integer item : nums){
	right += item;
	left = item > left ? item : left;
}

如何确定左右边界移动的条件？

解决了边界问题，下面来考虑边界移动的条件。

对于左右边界的中间元素mid，我们使用一种方法（该方法下文会讲到）统计所有满足元素之和不大于中间元素的不重复子数组的数量，记为count。当count > m时，说明mid偏小，符合条件的数组数量过多。我们设共可以分成n个数组，则每个数组中元素之和均小于mid，但由于要求划分为m个数组（m<n），必须将这n个数组中某几个合并，显然合并后的某些数组元素之和会大于等于mid，此时我们将左边界右移，增大mid的取值。当count <= m时，说明mid偏大或者正好符合要求，此时我们将右边界左移，减小mid的取值或跳出循环。

这里需要注意的一点是，由于待划分数组本身可看作一完整数组，故count的初始值设置为1。

使用什么方法统计元素之和小于中间元素的子数组数量？

最容易想到的方法就是循环遍历。维护一个temp变量用来计算遍历元素之和，当temp > mid时子数组元素之和大于mid，此时完成一个符合要求数组的扫描，令计数变量加1，将temp赋值为使数组元素之和大于mid的那个元素（这样满足题目非空连续子数组的要求）。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int splitArray(int[] nums, int m) {
        // 获取使用二分法的左右边界
        // left = max(nums[i]), right = sum(nums[i])
        int left = 0;
        int right = 0;
        for(Integer item : nums){
            right += item;
            left = item > left ? item : left;
        }

        while(left < right){
            int mid = (left + right) >>> 1;
            int count = 1;
            int temp = 0;
            for(Integer items : nums){
                temp += items;
                if(temp > mid){
                    temp = items;
                    count++;
                }
            }
            if(count > m){
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }
        return left;
    }
}

LeetCode-719.Find K-th Smallest Pair Distance

题目链接

719.Find K-th Smallest Pair Distance

题目描述

Difficulty: Hard

719.PNG-24.7kB

思路分析

本题目输入为一个未排序数组和整数k，需要编写函数计算数组中两两元素之间的距离（即元素绝对值之差），返回第k小的距离。针对本题我们可以使用二分查找+双指针的方法来解决。

如何确定二分法的左右边界？

题目要求两两元素距离，由于输入数组中存在元素相同的可能，故该距离最小值即二分法左边界为0；显然二分法右边界为数组中最大元素和最小元素之差。将数组排序之后，可以使用nums[nums.length - 1] - nums[0]来表示该值。

如何确定边界移动条件？

根据普通二分查找的模板，我们可以得到中间值mid，通过双指针移动统计满足两元素距离小于mid的所有数字对的数量并循环相加，设最终结果为count。若count >= k，说明满足条件的距离对过多，即最少获得第(k+1)小的距离对，此时需要将mid左移，从而导致在计数循环中开始指针持续右移，造成count减小，向题目要求k靠拢。否则说明满足条件的距离对过少，将mid右移。

边界移动代码如下：

1
2
3
4
5
6
7
8
if(count >= k){
// 该分支表示数量过多，即最少获得第(k+1)小的距离对
// 此时需要将mid左移，则在上一个循环中start继续右移，导致count减小；
	right = mid;
} 
else{
    left = mid + 1;
}

如何统计距离对小于mid的元素个数？

使用双指针移动的方法进行统计，每次维护起始指针start指向0，然后循环移动终止指针。如果两指针指向元素之差大于mid，则起始指针右移，否则统计end - start的值并将其累加到count上。代码如下：

1
2
3
4
5
6
7
int start = 0, count = 0;
for(int end = 0;end<nums.length;end++){
    // 通过滑动窗口下界线右移，满足出现一对距离小于等于mid的数字对停止
    // 此时(end - start)即为小于等于mid的数字对数量
    while(nums[end] - nums[start] > mid) start++;
    count += (end - start);
}

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);


        // 对于经过排序后的数组nums，其中元素的距离范围一定在0（出现重复元素）和nums[nums.length - 1] - nums[0]         （最大值与最小值之差）之间
        int left = 0;
        int right = nums[nums.length - 1] - nums[0];

        while(left < right){
            int mid = (left + right) >>> 1;
            int start = 0, count = 0;
            for(int end = 0;end<nums.length;end++){
                // 通过滑动窗口下界线右移，满足出现一对距离小于等于mid的数字对停止
                // 此时(end - start)即为小于等于mid的数字对数量
                while(nums[end] - nums[start] > mid) start++;
                count += (end - start);
            }
            if(count >= k){
                // 该分支表示数量过多，即最少获得第(k+1)小的距离对
                // 此时需要将mid左移，则在上一个循环中start继续右移，导致count减小；
                right = mid;
            } 
            else{
                left = mid + 1;
            }
        }
        return left;
    }
}

0x03 总结

对于二分查找法，推荐使用while(left < right)和left = mid + 1; right = mid对应的模板进行解题，该模板无需考虑返回值为left还是right，也无需考虑取中位数时是否需要向上取整。模板使用过程中如果出现死循环可以调整上下界来查看返回结果，对于可能出现的特殊情况需要单独讨论。

纵观这些二分法题目，我们可以得出一般规律，如果题目给出有序或半有序（多个有序数组的组合）数组，左右边界极大可能是数组中的元素（经常取nums[0]和nums[nums.length - 1]）；如果题目给出无序数组，左右边界极大可能为数组元素之间运算所得的结果，此时需要结合题目需求来确定。

请作者吃个小鱼饼干吧
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多